Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
All PLDs including FPGAs, provide special programmable circuits that can be used as external inputs or outputs for a circuit design implemented on the device. These are collectively referred to as I/O Sites (or I/O pins). The I/O blocks in a circuit design are assigned to the I/O sites in the PLD in a process that is collectively referred to as I/O Placement. The I/O sites allow the design implemented on the PLD to electrically connect with external devices and systems. Each I/O site and I/O block has a set of electrical parameters defined for it. This includes parameters like drive voltages Vcci and Vcco, reference voltage Vref, termination voltage Vr, drive strength, digitally controlled impedance (DCI) and termination. An allowed combination of these parameters is referred to as an I/O Standard. Each I/O site and I/O block is thus associated with an I/O standard. Examples for I/O standards can include LVCMOS33, LVCMOS25, LVTTL and LVDS25. I/O standards that require incompatible values for their electrical parameters are said to be incompatible with each other and vice versa.
Most modern PLDs organize I/O sites on the device into a limited number of physical I/O Banks (banks) on the PLD. A PLD, such as an FPGA, can include 8 banks, although this number is not definitive of every type of PLD as different PLDs can include different numbers of banks. The I/O sites in any given bank can share some or all of their electrical circuitry. Most commonly, the I/O sites in a bank share the Vcco, Vcci, Vref and Vr voltage supplies. Note that this sharing and other such conditions, introduces compatibility constraints for the I/O blocks that can be assigned to a bank and placement constraints for the assignment of individual I/O blocks to I/O sites within the bank.
The I/O blocks that are assigned to a given bank should be configured according to compatible I/O standards. For example, the I/O standard LVTTL requires a Vcco value of 3.3 volts, while the I/O standard LVDCI—18 requires 1.8 volts. Since the Vcco values do not match, a circuit cannot implement I/Os of these two I/O standards in the same I/O bank.
A second condition that arises in I/O banks is due to the dual purpose nature of some I/O sites in the bank. To conserve silicon area, some I/O sites on the bank can be used for both reference voltages (Vref, Vr) or for regular I/O blocks. If any I/O block that requires a reference voltage is assigned to a bank then some or all of the Vref/Vr sites in that bank should be used for the required voltage. These sites are then unavailable for other regular I/O blocks. For example, the I/O standard SSTL2_I requires a reference voltage Vref of 1.25 volts. If an I/O block of this standard is placed in a bank, then all Vref sites in that bank are reserved for the reference voltage and no other I/O block of any I/O standard can be placed on the Vref sites in that bank. Conversely, if no I/O block that requires a reference voltage is assigned to a bank, then all Vref sites in that bank are usable for regular I/O blocks.
A third condition that arises in I/O banks is due to the placement constraint of Relationally Placed Macros (RPMs) in the circuit design. An I/O RPM is made up of 2 or more I/O blocks that have to be placed in a predefined relative form. A common example of I/O RPMs is differential I/O (LVDS) pairs. These consist of two I/O blocks, namely a master and a slave, that are generally required to be placed together, adjacent to each other, in a predefined orientation. Note that a typical circuit design implemented in PLDs may have a mix of both RPM I/Os and single (non-RPM) I/O blocks. Consider an I/O bank with 10 I/O sites. An assignment of 8 single I/O blocks and 1 I/O RPM of two I/O blocks (all with compatible I/O standards) to this bank is perfectly legal from an assignment point of view and is illustrated below:
If the single I/O blocks are placed such that two adjacent I/O sites are available (A), then the I/O RPM has a legal placement available. However, if the single I/O blocks are placed such that no two adjacent sites are available (B), then the I/O RPM cannot be placed anywhere in the bank.
A fourth condition that arises in I/O banks is due to the fact that a given I/O bank may consist of I/O sites of different types. A given I/O block in a design may be placed on only a subset of the I/O sites in a bank. For example, an I/O bank with 20 sites in total may have 10 Clock-IO sites that are capable of driving global clock buffers in the FPGA device. An assignment of 10 Clock-IO blocks and 10 non-Clock-IO blocks from a design to this bank is perfectly legal from an assignment point of view. However, if all 10 of the non-Clock-IO blocks are placed onto the 10 Clock-IO sites in the bank, then the Clock-IO blocks cannot be assigned to any sites in the bank.
A fifth condition that arises in I/O banks is due to user imposed placement constraints on I/O blocks. For various reasons, the user might restrict the placement of an I/O block to a subset of the I/O sites in a bank. These placement constraints are collectively referred to as Range Constraints. Note that range constraints may also be imposed by the tools themselves, without any user input. For example, consider an I/O bank with 10 I/O sites. Six I/O blocks (with compatible I/O standards) are assigned to this bank. One of the I/O blocks has been range constrained to the left half of the I/O bank, meaning that it has to be placed on any of the 5 I/O sites on the left-hand-side of the bank. In C shown below, the 5 I/O blocks that are not range-constrained have been placed on the 5 I/O sites on the right-hand-side of the bank. Hence the one range-constrained block can be placed on any of the free I/O sites on the left-hand-side. However if the 5 unconstrained I/O blocks are placed on the left-hand-side of the bank (D), then the range-constrained I/O block cannot be placed on any I/O site in the bank leading to an I/O placement failure.

For all of these programmable logic devices (PLDs), the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, e.g., using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable. For example, one type of PLD includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
FIG. 1 is a block diagram of an exemplary FPGA. As noted above, advanced FPGAs can include several different types of programmable logic blocks in the array. For example, FIG. 1 illustrates an FPGA architecture 100 that includes a large number of different programmable tiles including multi-gigabit transceivers (MGTs 101), configurable logic blocks (CLBs 102), random access memory blocks (BRAMs 103), input/output blocks (IOBs 104), configuration and clocking logic (CONFIG/CLOCKS 105), digital signal processing blocks (DSPs 106), specialized input/output blocks (I/O 107) (e.g., configuration ports and clock ports), and other programmable logic 108 such as digital clock managers, analog-to-digital converters, system monitoring logic, and so forth. Some FPGAs also include dedicated processor blocks (PROC 110).
In some FPGAs, each programmable tile includes a programmable interconnect element (INT 111) having standardized connections to and from a corresponding interconnect element in each adjacent tile. Therefore, the programmable interconnect elements taken together implement the programmable interconnect structure for the illustrated FPGA. The programmable interconnect element (INT 111) also includes the connections to and from the programmable logic element within the same tile, as shown by the examples included at the top of FIG. 1.
For example, a CLB 102 can include a configurable logic element (CLE 112) that can be programmed to implement user logic plus a single programmable interconnect element (INT 111). A BRAM 103 can include a BRAM logic element (BRL 113) in addition to one or more programmable interconnect elements. Typically, the number of interconnect elements included in a tile depends on the height of the tile. In the pictured embodiment, a BRAM tile has the same height as four CLBs, but other numbers (e.g., five) can also be used. A DSP tile 106 can include a DSP logic element (DSPL 114) in addition to an appropriate number of programmable interconnect elements. An IOB 104 can include, for example, two instances of an input/output logic element (IOL 115) in addition to one instance of the programmable interconnect element (INT 111). As will be clear to those of skill in the art, the actual I/O pads connected, for example, to the I/O logic element 115 are manufactured using metal layered above the various illustrated logic blocks, and typically are not confined to the area of the input/output logic element 115.
In the pictured embodiment, a columnar area near the center of the die (shown shaded in FIG. 1) is used for configuration, clock, and other control logic. Horizontal areas 109 extending from this column are used to distribute the clocks and configuration signals across the breadth of the FPGA.
Some FPGAs utilizing the architecture illustrated in FIG. 1 include additional logic blocks that disrupt the regular columnar structure making up a large part of the FPGA. The additional logic blocks can be programmable blocks and/or dedicated logic. For example, the processor block PROC 110 shown in FIG. 2 spans several columns of CLBs and BRAMs.
Note that FIG. 1 is intended to illustrate only an exemplary FPGA architecture. For example, the numbers of logic blocks in a column, the relative width of the columns, the number and order of columns, the types of logic blocks included in the columns, the relative sizes of the logic blocks, and the interconnect/logic implementations included at the top of FIG. 1 are purely exemplary. For example, in an actual FPGA more than one adjacent column of CLBs is typically included wherever the CLBs appear, to facilitate the efficient implementation of user logic, but the number of adjacent CLB columns varies with the overall size of the FPGA.
FIG. 2 is a simplified diagram of a well known Complex Programmable Logic Device (CPLD) architecture. FIG. 2 is a simplified illustration of an exemplary CPLD. A CPLD typically includes two or more logic blocks (LBs 201a-201h) connected together and to input/output blocks (I/Os 202a-202f) by a programmable interconnection array (203). Each logic block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (PLAs) and Programmable Array Logic (PAL) devices. The interconnection array includes many multiplexer circuits 205, each including several PIPs 204. In each multiplexer circuit 205, only one PIP 204 is enabled. The enabled PIP selects one of the many input signals provided to the interconnection array, and the selected input signal is provided as the output signal from the multiplexer circuit 205.
In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration sequence.
Further information on CPLDs can be found, for example, in U.S. Pat. No. 6,466,049 B1 by Sholeh Diba et al., issued Oct. 15, 2002, which is hereby incorporated herein by reference.
One such FPGA, the Xilinx Virtex® FPGA, is described in detail in pages 3-75 through 3-96 of the Xilinx 2000 Data Book entitled “The Programmable Logic Data Book 2000” (hereinafter referred to as “the Xilinx Data Book”), published April, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference. (Xilinx, Inc., owner of the copyright, has no objection to copying these and other pages referenced herein but otherwise reserves all copyright rights whatsoever.) Young et al. further describe the interconnect structure of the Virtex FPGA in U.S. Pat. No. 5,914,616, issued Jun. 22, 1999 and entitled “FPGA Repeatable Interconnect Structure with Hierarchical Interconnect Lines”, which is incorporated herein by reference in its entirety.
One such FPGA, the Xilinx Virtex®-II FPGA, is described in detail in pages 33-75 of the “Virtex-II Platform FPGA Handbook”, published December, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference.
Another such FPGA, the Xilinx Virtex-II Pro™ FPGA, is described in detail in pages 19-71 of the “Virtex-II Pro Platform FPGA Handbook”, published Oct. 14, 2002 and available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference.
As FPGA designs increase in complexity, they reach a point at which the designer cannot deal with the entire design at the gate level. Where once a typical FPGA design comprised perhaps 5,000 gates, FPGA designs with over 100,000 gates are now common. To deal with this complexity, circuits are typically partitioned into smaller circuits that are more easily handled. Often, these smaller circuits are divided into yet smaller circuits, imposing on the design a multi-level hierarchy of logical blocks.
Libraries of pre-developed blocks of logic have been developed that can be included in an FPGA design. Such library modules include, for example, adders, multipliers, filters, and other arithmetic and DSP functions from which complex designs can be readily constructed. The use of pre-developed logic blocks permits faster design cycles, by eliminating the redesign of duplicated circuits. Further, such blocks are typically well tested, thereby making it easier to develop a reliable complex design.
All modern FPGAs use a banked I/O organization with a specified number of I/O banks of certain capacities, and set of restrictions (banking rules) that specify which I/O blocks can be combined in the same I/O bank. Thus the placement of I/O blocks is subject to a set of constraints imposed by the bank organization (and available resources), and various compatibility rules. Such problems belong to the class of “constrained optimization problems”.
Modern approaches to such constrained optimization problems often use a “separation principle” that splits the complete problem into 2 separate tasks. The first task involves a pure assignment problem and a second task involves a sequential placement problem. The assignment task does not attempt to place all I/O blocks into available sites physically, but merely assigns all movable unlocked I/O blocks to the I/O banks in a way that satisfies all relevant constraints. The main purpose of the “assignment problem” is to prove the feasibility of a design and in the case of a feasible design to provide one or more feasible assignment solutions. The set of feasible solutions can optionally be improved at a later stage to optimize for other cost functions like wire-length, timing constraints or other constraints.
The second task includes the physical placement of I/O blocks assigned to an I/O bank to I/O sites available within a given bank. Existence of a feasible solution for the assignment task guarantees that only compatible I/O blocks are assigned to a bank and that the bank's capacity is sufficient to accommodate all assigned I/O blocks. Nonetheless, physical placement within I/O banks is still a non-trivial problem because some sites may not be available for usage by some I/O blocks. It is also much more complicated when the set of assigned I/O blocks are part of Relatively Placed Modules (RPMs). An RPM is a set of blocks with predefined relative coordinates.
Traditional methods of intra-bank placement can be broadly classified as one of two types. A first type can use heuristics that tries direct sequential placement of an ordered set of I/O blocks to an ordered set of I/O sites. In all cases ordering of I/O blocks should be predefined and constitutes a part of placement algorithm. For simple cases, the heuristic approach is frequently sufficient. Its main drawback is the very strong dependency on the ordering. In a difficult situation, it frequently assigns some I/O blocks to the first available and compatible sites, while leaving some other I/O blocks without sufficient and suitable I/O sites. It is also extremely difficult to use in situations when there are non-uniform sets of I/O blocks (e.g., clock IOs and regular Select IOs) that have different compatibility to available sites.
A second type of intra-bank placement can use a more generic bi-partite matching that tries to find best placement of the set of I/O blocks to the set of I/O sites using some static cost functions. This method is much better for many situations, but it has a lot of inconsistencies when applied to a mix of single IOs and IOs that are part of RPMs. As a result, for such situations, the method convergence is bad and results are not reliable. Also note, it is a common feature of all heuristic approaches that they cannot prove the existence of a feasible placement solution or the lack of it.